ON CIRCUITS BEING ASYMPTOTICALLY OPTIMAL BY RELIABILITY IN CASES OF GATE FAILURES 

Alekhina Marina Anatol'evna, Doctor of physical and mathematical sciences, professor, head of sub-department of mathematics, Penza State Technological University (1a/1 Baydukova lane/Gagrina street, Penza, Russia), ama@sura.ru

519.718

10.21685/2072-3040-2016-4-6

Background. The increase of complexity of modern systems of data processing, transmission and storage emphasizes a requirement of safety and monitoring over various control and computing systems. The article is devoted to topical problems of formation of circuits, asymptotically optimal by reliability, that realize Boolean functions in cases of random gate failures in the basis consisting of the “anticonjuction” function. The aim of the work is to find answers to the following questions: Is it possible to realize an arbitrary Boolean function by a circuit with asymptotically optimal reliability and how unreliable is the said circuit?
Materials and methods. The study applied previously known methods of reliable circuit synthesis and circuit reliability estimation.
Results. It has been proved that virtually any Boolean function mya be realized by a circuit with asymptotically optimal reliability. The article shows the upper and lower estimates of unreliability of the said circuit. The obtained results may be used in technical system design in order ot increase their reliability.
Conclusions. In the case of random gate failures in the basis consisting of the “anticonjunction” function it is possible to realize virtually any Boolean function by a circuit with asymptotically optimal reliability.

unreliable functional gates, reliability of circuits, unreliability of circuits, failures on inputs of gates

1. Romanov D. S. Prikladnaya matematika i informatika [Applied mathematics and informatics]. 2010,vol.36,p.91.
2. Romanov D. S. Computational Mathematics and Modeling. 2012, vol. 23, pp. 72–78.
3. Morozov E. V., Romanov D. S. Diskretnyy analiz i issledovanie operatsiy [Discrete analysis and research of operations]. 2015, vol. 22, no. 1, pp. 49–61.
4. Morozov E. V., Romanov D. S. Diskretnaya matematika i ee prilozheniya: materialy XI Mezhdunar. seminara, posvyashch. 80-letiyu so dnya rozhd. akad. O. B. Lupanova
(Moskva, MGU, 18–23 iyunya 2012 g.) [Discete mathematics and its applications: proceedings of XI International seminar devoted to the 80th anniversary of academician O.B. Lupanov (Moscow, MSU, 18th – 23rd June 2012)]. Moscow: Izd-vo mekhanikomatematicheskogo fak-ta MGU, 2012, pp. 144–147.
5. Alekhina M. A. Vestnik Moskovskogo universiteta. Matematika. Mekhanika [Bulletin of Moscow University. Mathematics. Mechanics]. 1991, no. 5, pp. 80–83.
6. Alekhina M. A. Diskretnaya matematika [Discrete mathematics]. 1993, vol. 5, no. 2, pp. 59–74.
7. Alekhina M. A. Diskretnyy analiz i issledovanie operatsiy. Ser. 1 [Discrete analysis and research of operations. Series 1]. 2005, vol. 12, pp. 3–11.
8. Alekhina M. A., Logvina O. A. Prikladnaya diskretnaya matematika. Prilozhenie [Applied discrete mathematics. Applications]. 2016, no. 9, pp. 98–100.
9. Alekhina M. A., Barsukova O. Yu. Computer Science and Information Technology. 2014, vol 2(1), pp. 51–54. DOI: 10.13189/csit.2014.020106.
10. Alekhina M. A. Izvestiya vysshikh uchebnykh zavedeniy. Povolzhskiy region. Fizikomatematicheskie nauki [University proceedings. Volga region. Physical and mathematical sciences]. 2015, no. 2 (34), pp. 3–15.
11. Izbrannye trudy S. V. Yablonskogo [Selected works of S. V. Yablonsky]. Execut. ed. V. B. Alekseev, V. I. Dmitriev. Moscow: MAKS Press, 2004.
12. Tarasov V. V. Matematicheskie zametki [Mathematical proceedings]. 1976, vol. 20, no. 3, pp. 391–400.
13. Alekhina M. A. Sintez, slozhnost' i nadezhnost' skhem iz nenadezhnykh funktsional'nykh elementov: dis. d-ra fiz.-mat. nauk [Synthesis, complexity and reliability of circuits consisting of unreliable functional gates: dissertation to apply for the degree of the doctor of physical and mathematical sciences]. Penza, 2004.